home *** CD-ROM | disk | FTP | other *** search
/ PC World Komputer 2001 December / pcwk12201b.iso / Wersje pelne i specjalne / Winamp 2.77 i 3.0beta / wasabi-sdk_beta1.exe / studio / common / ptrlist.h < prev    next >
C/C++ Source or Header  |  2001-10-08  |  10KB  |  352 lines
  1. /*
  2.  
  3.   Nullsoft WASABI Source File License
  4.  
  5.   Copyright 1999-2001 Nullsoft, Inc.
  6.  
  7.     This software is provided 'as-is', without any express or implied
  8.     warranty.  In no event will the authors be held liable for any damages
  9.     arising from the use of this software.
  10.  
  11.     Permission is granted to anyone to use this software for any purpose,
  12.     including commercial applications, and to alter it and redistribute it
  13.     freely, subject to the following restrictions:
  14.  
  15.     1. The origin of this software must not be misrepresented; you must not
  16.        claim that you wrote the original software. If you use this software
  17.        in a product, an acknowledgment in the product documentation would be
  18.        appreciated but is not required.
  19.     2. Altered source versions must be plainly marked as such, and must not be
  20.        misrepresented as being the original software.
  21.     3. This notice may not be removed or altered from any source distribution.
  22.  
  23.  
  24.   Brennan Underwood
  25.   brennan@nullsoft.com
  26.  
  27. */
  28.  
  29. #ifndef _PTRLIST_H
  30. #define _PTRLIST_H
  31.  
  32. #include "std.h"
  33. #include "common.h"
  34. #include "../studio/assert.h"
  35.  
  36. /*
  37.  
  38. a generic pointer list template. only takes up 12 bytes when empty. auto-grows
  39. the array as necessary, NEVER shrinks it unless you removeAll() or equivalent
  40.  
  41. Use, PtrList<typename>, never PtrListRoot
  42.  
  43. */
  44.  
  45. #define POS_LAST -1
  46.  
  47. // 1k each, leaving 16 bytes for MALLOC overhead
  48. #define DEF_PTRLIST_INCREMENT 252
  49.  
  50. // base class, to share as much code as possible
  51. class COMEXP NOVTABLE PtrListRoot {
  52. protected:
  53.   PtrListRoot(int initial_size=0);
  54.   ~PtrListRoot();
  55.  
  56.   void copyFrom(const PtrListRoot *from);
  57.  
  58.   void setMinimumSize(int nslots);    // expand to at least this many slots
  59.   int getNumItems() const { return nitems; };
  60.  
  61.   void *enumItem(int n) const;
  62.  
  63.   void moveItem(int from, int to);
  64.  
  65.   int removeItem(void *item);
  66.   void removeEveryItem(void *item);
  67.   void removeByPos(int pos);
  68.   void removeLastItem();
  69.   void removeAll();
  70.   void freeAll();
  71.  
  72.   // gross-ass linear search to find index of item
  73.   // note that PtrListSorted provides a binary search version
  74.   int searchItem(void *item) const;
  75.  
  76. #if 0//fuct
  77.   // speedy binary search. although it'll be fuct if it's not sorted right
  78.   int bsearchItem(void *item) const;
  79. #endif
  80.  
  81.   void *addItem(void *item, int pos, int inc);
  82.  
  83.   void **getItemList() const;    // try to avoid!
  84.  
  85. private:
  86.   int nitems, nslots;
  87.   void **items;
  88. };
  89.  
  90. // now we add the methods that refer specifically to the pointer type
  91. template<class T>
  92. class PtrList : private PtrListRoot {
  93. public:
  94.   PtrList(int initial_size=0) : PtrListRoot(initial_size) {}
  95.   PtrList(const PtrList<T> &r) {
  96.     copyFrom(&r);
  97.   }
  98.   ~PtrList() {}
  99.  
  100.   // copy another PtrList
  101.  
  102.   void copyFrom(const PtrList<T> *from) { PtrListRoot::copyFrom(from); }
  103.  
  104. // adding
  105.  
  106.   // expand freelist to at least this many slots, even if 0 items in list
  107.   void setMinimumSize(int nslots) { PtrListRoot::setMinimumSize(nslots); }
  108.  
  109.   // provide a public addItem for the pointer type
  110.   T *addItem(const T *item, int pos=POS_LAST, int inc=DEF_PTRLIST_INCREMENT) {
  111.     return static_cast<T *>(PtrListRoot::addItem(const_cast<T*>(item), pos, inc));
  112.   }
  113.  
  114. // enumerating
  115.  
  116.   // returns # of items in list
  117.   int getNumItems() const { return PtrListRoot::getNumItems(); }
  118.  
  119.   // basic list enumerator. returns NULL for out of bounds
  120.   T *enumItem(int n) const {
  121.     return static_cast<T *>(PtrListRoot::enumItem(n));
  122.   }
  123.   T *operator[](int n) const { return enumItem(n); }
  124.  
  125.   // this will safely return NULL if 0 items due to enumItems's boundscheck
  126.   T *getFirst() const { return enumItem(0); }
  127.   T *getLast() const { return enumItem(getNumItems()-1); }
  128.  
  129.   // gross-ass linear search to find index of item
  130.   // note that PtrListSorted provides a binary search version
  131.   int searchItem(T *item) const { return PtrListRoot::searchItem(item); }
  132.   int haveItem(T *item) const { return searchItem(item) >= 0; }
  133.  
  134. // deleteing
  135.  
  136.   // removes first instance of a pointer in list, returns how many are left
  137.   int removeItem(T *item) { return PtrListRoot::removeItem(item); }
  138. //DEPRECATED
  139. int delItem(T *item) { return removeItem(item); }
  140.   // removes all instances of this pointer
  141.   void removeEveryItem(void *item) { PtrListRoot::removeEveryItem(item); }
  142.   // removes pointer at specified position regardless of value
  143.   void removeByPos(int pos) { PtrListRoot::removeByPos(pos); }
  144. // DEPRECATED
  145. void delByPos(int pos) { removeByPos(pos); }
  146.  
  147.   // removes last item
  148.   void removeLastItem() { PtrListRoot::removeLastItem(); }
  149.   // removes all entries, also deletes memory space
  150.   void removeAll() { PtrListRoot::removeAll(); }
  151.   // removes all entries, calling FREE on the pointers
  152.   void freeAll() { PtrListRoot::freeAll(); }
  153.   // removes all entries, calling delete on the pointers
  154.   void deleteAll() {
  155.     int i, nitems = getNumItems();
  156.     for (i = 0; i < nitems; i++)
  157.       delete enumItem(i);
  158.     removeAll();
  159.   }
  160.   // removes all entries, calling delete on the pointers
  161.   // FG>this version removes each entry as it deletes it so if
  162.   // one of the object uses this list in its destructor, it will
  163.   // still work. It is MUCH slower than deleteAll tho.
  164.   void deleteAllSafe() {
  165. //CUT    ASSERT(!(nitems != 0 && items == NULL));
  166.     while (getNumItems()) {
  167.       T *i = enumItem(0);
  168.       delete i;
  169.       removeItem(i);
  170.     }
  171.   }
  172.  
  173.   void moveItem(int from, int to) { PtrListRoot::moveItem(from, to); }
  174.  
  175. protected:
  176.   T **getItemList() {
  177.     return reinterpret_cast<T **>(PtrListRoot::getItemList());
  178.   }
  179. };
  180.  
  181. class NotSorted {
  182. public:
  183.   // comparator for searching -- override
  184.   static int compareAttrib(const char *attrib, void *item) { return 0; }
  185.   // comparator for sorting -- override    , -1 p1 < p2, 0 eq, 1 p1 > p2
  186.   static int compareItem(void *p1, void* p2) { return 0; }
  187. };
  188.  
  189. //template <class T, class C> class NoSort {
  190. //  static void _sort(T **, int) {}
  191. //};
  192.  
  193. // a base class to sort the pointers
  194. // you must implement the comparisons (C) and the sort algorithm (S)
  195. template< class T, class C, class S >
  196. class PtrListSorted : public PtrList<T> {
  197. public:
  198.   PtrListSorted(int initial_size=0) : PtrList<T>(initial_size) {
  199.     need_sorting = 0;
  200.     auto_sort = 1;
  201.   }
  202.  
  203.   void copyFrom(const PtrList<T> *from) {
  204.     PtrList<T>::copyFrom(from);
  205.     need_sorting = 1;
  206.     if (auto_sort) sort();
  207.   }
  208.  
  209.   T *addItem(T *item, int pos=POS_LAST, int inc=DEF_PTRLIST_INCREMENT) {
  210.     need_sorting = 1;
  211.     return PtrList<T>::addItem(item, pos, inc);
  212.   }
  213.  
  214.   void sort(BOOL force_sort=FALSE) {
  215.     if (need_sorting || force_sort)
  216.       S::_sort(PtrList<T>::getItemList(), getNumItems());
  217.     need_sorting = 0;
  218.   }
  219.  
  220.   T *enumItem(int n) {    // NOT const since we might call sort()
  221.     if (auto_sort) sort();
  222.     return PtrList<T>::enumItem(n);
  223.   }
  224.   T *operator[](int n) { return PtrListSorted<T,C,S>::enumItem(n); }
  225.  
  226.   T *findItem(const char *attrib, int *pos=NULL) {
  227.     ASSERTPR(!(!auto_sort && need_sorting), "must call sort() first if auto-sorting is disabled");
  228.     sort();
  229. #if 1    // do binary search
  230.     if (getNumItems() == 0) return NULL;
  231.  
  232.     int bot = 0, top = getNumItems()-1, mid;
  233.  
  234.     for (int c = 0; c < getNumItems()+1; c++) {
  235.       if (bot > top) return NULL;
  236.       mid = (bot + top) / 2;
  237.       int r = C::compareAttrib(attrib, getItemList()[mid]);
  238.       if (r == 0) {
  239.         if (pos != NULL) *pos = mid;
  240.         return getItemList()[mid];
  241.       }
  242.       if (r < 0) {
  243.         top = mid-1;
  244.       } else {
  245.         bot = mid+1;
  246.       }
  247.     }
  248.     ASSERTPR(0, "binary search fucked up");
  249. #else
  250.     // re-enable this in case of fuckup
  251.     for (int i = 0; i < nitems; i++) {
  252.       if (C::compareAttrib(attrib, static_cast<T *>(items[i])) == 0) return static_cast<T *>items[i];
  253.     }
  254. #endif
  255.     return NULL;
  256.   }
  257.  
  258.   T *findItem(T *attrib, int *pos=NULL) {
  259.     return findItem((const char *)attrib, pos);
  260.   }
  261.  
  262. #if 0
  263.   // replace search with binary search
  264.   int searchItem(T *item) const {
  265.     ASSERTPR(!(!auto_sort && need_sorting), "must call sort() first if auto-sorting is disabled");
  266.     sort();
  267.     return bsearchItem(item);
  268.   }
  269. #endif
  270.  
  271.   void setAutoSort(int as) {
  272.     auto_sort = as;
  273.   }
  274.   int getAutoSort() const {
  275.     return auto_sort;
  276.   }
  277.  
  278.   void removeDups() {
  279.     ASSERTPR(!(!auto_sort && need_sorting), "must call sort() first if auto-sorting is disabled");
  280.     sort();
  281.     for (int i = 1; i < getNumItems(); i++) {
  282.       if (C::compareItem(enumItem(i-1), enumItem(i)) == 0) {
  283.         delByPos(i);
  284.         i--;
  285.       }
  286.     }
  287.   }
  288.  
  289. private:
  290.   int need_sorting;
  291.   int auto_sort;
  292. };
  293.  
  294. // quicksort -- you still need to override the compare fns
  295. template<class T, class C>
  296. class QuickSorted {
  297. public:
  298.   static void _sort(T **items, int nitems) {
  299.     if (items == NULL || nitems <= 1) return;
  300.     Qsort(items, 0, nitems-1);
  301.   }
  302.  
  303. private:
  304.   static void swapItem(T **items, int a, int b) { // no bounds checking!
  305.     T *tmp = items[a];
  306.     items[a] = items[b];
  307.     items[b] = tmp;
  308.   }
  309.  
  310.   static void Qsort(T **items, int lo0, int hi0) {
  311.     int lo = lo0, hi = hi0;
  312.     if (hi0 > lo0) {
  313.       T *mid = items[(lo0 + hi0) / 2];
  314.       while (lo <= hi) {
  315.         while ((lo < hi0) && (C::compareItem(items[lo], mid) < 0)) lo++;
  316.         while ((hi > lo0) && (C::compareItem(items[hi], mid) > 0)) hi--;
  317.  
  318.         if (lo <= hi) {
  319.           swapItem(items, lo, hi);
  320.           lo++;
  321.           hi--;
  322.         }
  323.       }
  324.  
  325.       if (lo0 < hi) Qsort(items, lo0, hi);
  326.       if (lo < hi0) Qsort(items, lo, hi0);
  327.     }
  328.   }
  329. };
  330.  
  331. // easy way to specify quicksorting, just data type and comparison class
  332. template <class T, class C> class PtrListQuickSorted : public PtrListSorted<T, C, QuickSorted<T, C> > {
  333. public:
  334.   PtrListQuickSorted(int initial_size=0) : PtrListSorted<T, C, QuickSorted<T, C> >(initial_size) {}
  335. };
  336.  
  337.  
  338. // easy way to get a list sorted by pointer val
  339. class SortByPtrVal {
  340. public:
  341.   static int compareItem(void *p1, void *p2) {
  342.     return CMP3(p1, p2);
  343.   }
  344.   static int compareAttrib(const char *attrib, void *item) {
  345.     return CMP3((void *)attrib, item);
  346.   }
  347. };
  348.  
  349. template <class T> class PtrListQuickSortedByPtrVal : public PtrListQuickSorted<T, SortByPtrVal > {};
  350.  
  351. #endif
  352.